#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode *left;  //左孩子节点
    struct BinaryTreeNode *right; //右孩子节点
    BTDataType val;
} BTNode;

//构造节点
BTNode *BuyBTNode(BTDataType x)
{
    BTNode *p = (BTNode *)malloc(sizeof(BTDataType));
    if (p == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    p->val = x;
    p->left = p->right = NULL;

    return p;
}

//构造二叉树
BTNode *CreatBinaryTree()
{
    BTNode *node1 = BuyBTNode(1);
    BTNode *node2 = BuyBTNode(2);
    BTNode *node3 = BuyBTNode(3);
    BTNode *node4 = BuyBTNode(4);
    BTNode *node5 = BuyBTNode(5);
    BTNode *node6 = BuyBTNode(6);

    node1->left = node2;
    node2->left = node3;
    node1->right = node4;
    node4->left = node5;
    node4->right = node6;

    //返回根节点
    return node1;
}

//前序遍历
void PrevOrdef(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->val);
    PrevOrdef(root->left);
    PrevOrdef(root->right);
}

//中序遍历
void InOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->val);
    InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->val);
}

//层序遍历->使用队列实现->注意：这里入队列入的是二叉树的根节点指针，不是跟节点的值，入值找不到左右子树的地址
void LevelOrder(BTNode *root)
{
    //声明队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root);

    //当队列为空就停止循环
    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        printf("%d ", front->val); //出一个打印一个数据

        //判断根节点(front)的左子树和右子树是否为空，不为空就继续入队列
        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");

    //释放队列，防止内存泄漏
    QueueDestory(&q);
}

//判断是否为完全二叉树
bool BTreeComplete(BTNode *root)
{
    //创建队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root); //根节点入队列

    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //如果节点为叶节点，则不用继续入出队列了
        if (front == NULL)
            break;

        //这里不用判断节点是否为空，因为"空"也一起进队列
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }

    //判断剩余没出队列的数据，全是叶节点(左右子树都为NULL)则为完全二叉树
    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //判断队列中数据是否为全空，如果不是"全空"则不是完全二叉树.
        // 空后面出到非空，那么说明不是完全二叉树
        if (front)
            //释放队列，防止内存泄漏
            QueueDestory(&q);
        return false;
    }

    //释放队列，防止内存泄漏
    QueueDestory(&q);
    return true;
}

//节点个数----分治->左子树加右子树最后加上根节点就能得到全部节点的数量
int BTreeSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

//遍历计数方法比分治效率差一些，并且多了一个指针参数的内存空间
void BTreeSize2(BTNode *root, int *pi)
{
    if (root == NULL)
        return;
    //前序遍历计数
    ++(*pi);
    BTreeSize2(root->left, pi);
    BTreeSize2(root->right, pi);
}

//分治----求叶节点个数
int BTreeLeafSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    else if (root->left == NULL && root->right == NULL)
        return 1;
    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

//第k层的节点个数->根节点为第一个层
int BTreeKLevelSize(BTNode *root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

//二叉树的高度
int BTreeDepth(BTNode *root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BTreeDepth(root->left);
    int rightDepth = BTreeDepth(root->right);

    return leftDepth > rightDepth
               ? leftDepth + 1
               : rightDepth + 1;
}

// 二叉树查找值为x的节点
BTNode *TreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
        return NULL;

    if (root->val == x)
        return root;

    //判断左子树是否有值为x的节点
    BTNode *left_subTree = TreeFind(root->left, x);
    if (left_subTree)
        return left_subTree;

    //判断右子树是否有值为x的节点
    BTNode *right_subTree = TreeFind(root->right, x);
    if (right_subTree)
        return right_subTree;

    //没有找到则返回空指针
    return NULL;
}

void BinaryTreeDestory(BTNode **root)
{
    if (*root == NULL)
        return;
    BinaryTreeDestory(&((*root)->left));
    BinaryTreeDestory(&((*root)->right));
    free(*root);
    *root = NULL;
}

int main()
{
    BTNode *Tree = CreatBinaryTree();
    //前序遍历
    printf("前序遍历: ");
    PrevOrdef(Tree);
    printf("\n");

    //中序遍历
    printf("中序遍历: ");
    InOrder(Tree);
    printf("\n");

    //后序遍历
    printf("后序遍历: ");
    PostOrder(Tree);
    printf("\n");

    //层序遍历
    printf("层序遍历: ");
    LevelOrder(Tree);

    printf("二叉树的节点个数为: %d\n", BTreeSize(Tree));

    int count = 0;
    BTreeSize2(Tree, &count);
    printf("二叉树的节点个数为: %d\n", count);

    printf("二叉树的叶节点个数为: %d\n", BTreeLeafSize(Tree));

    int k = 3;
    printf("二叉树第%d层的节点为: %d\n", k, BTreeKLevelSize(Tree, k));

    printf("二叉树的高度为: %d\n", BTreeDepth(Tree));

    for (int i = 1; i < 8; ++i)
    {
        printf("x: %d, 地址: %p\n", i, TreeFind(Tree, i));
    }

    printf("判断是否为完全二叉树: %d\n", BTreeComplete(Tree));

    //释放二叉树
    // BinaryTreeDestory(&Tree);
    system("pause");
    return 0;
}